1178D - Prime Graph - CodeForces Solution

def isprime(x):
    if x == 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

def getrange(n):
    lower = n
    upper = n + n // 2
    return (lower, upper)

def main():
    
                                    
    n = int(input())
    if n <= 2:
        print(-1)
    
    lower, upper = getrange(n)
    p = -1
    for x in range(lower, upper + 1):
        if isprime(x):
            p = x
            break
    
    print(p)
    
    edges = []
    for i in range(n):
        edges.append((1 + i, 1 + ((i + 1) % n)))
    
    l, r = 0, n // 2
    while len(edges) < p:
        edges.append((1 + l, 1 + (r % n)))
        l += 1; r += 1
    multiLineArrayOfArraysPrint(edges)
    
    return

import sys
input=sys.stdin.buffer.readline  
def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr):     dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
 
inf=float('inf')
 
from math import gcd,floor,ceil
import math
 
for _abc in range(1):
    main()